package 力扣日常刷题.木22一月.第01天0108;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/8
 * @description
 */
public class Demo04并查集计算除法 {




    int[] p;
    double[] w;
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int nvars = 0;
        // variables  变量
        HashMap<String, Integer> variables = new HashMap<String, Integer>();
        int n = equations.size();
        for (int i = 0; i < n; i++) {
            if(!variables.containsKey(equations.get(i).get(0))){
                variables.put(equations.get(i).get(0),nvars++);
            }
            if(!variables.containsKey(equations.get(i).get(1))){
                variables.put(equations.get(i).get(1),nvars++);
            }
        }
        p = new int[nvars];
        w = new double[nvars];
        Arrays.fill(w,1.0);
        for (int i = 0; i < nvars; i++) {
            p[i] = i;
        }

        for (int i = 0; i < n; i++) {
            // 获得对应字符对应的index 作为索引
            int va = variables.get(equations.get(i).get(0)), vb = variables.get(equations.get(i).get(1));
            union(va,vb,values[i]);
        }
        int queriesCount = queries.size();
        double[] res = new double[queriesCount];

        for (int i = 0; i < queriesCount; i++) {
            List<String> query = queries.get(i);
            double result = -1.0;
            if(variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {
                int va = variables.get(query.get(0)), vb = variables.get(query.get(1));
                int pa = find(va),pb = find(vb);
                if(pa==pb){
                    result = w[va]/w[vb];
                }
            }
            res[i] = result;
        }
        return res;
    }

    public int find(int x){
        /**
        if(x!=p[x]) {
         // 压缩路径了  不可以这样  权值 压缩
            p[x] = find(p[x]);
            w[x] = w[x] * w[p[x]];
        }
        */
        if(x!=p[x]) {
            int f = find(p[x]);
            w[x] = w[x] * w[p[x]];
            p[x] = f;
        }
        return p[x];
    }

    public void union(int x,int y,double val){
        int px = find(x);
        int py = find(y);
        p[px] = py;
        w[px] = val * w[y] / w[x];
    }



}
